#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret(n, vector<int>(n));
        vector<vector<int>> v(n, vector<int>(n));
        int left = 0, right = n - 1, up = 0, down = n - 1;
        int k = 1;
        while (true)
        {
            for (int i = left; i <= right; i++)
            {
                if (v[up][i] != 0) continue;
                v[up][i] = k++;
            }
            if (++up > down) break;
            for (int i = up; i <= down; i++)
            {
                if (v[i][right] != 0) continue;
                v[i][right] = k++;
            }
            if (--right < left) break;
            for (int i = right; i >= left; i--)
            {
                if (v[down][i] != 0) continue;
                v[down][i] = k++;
            }
            if (--down < up) break;
            for (int i = down; i >= up; i--)
            {
                if (v[i][left] != 0) continue;
                v[i][left] = k++;
            }
            if (++left > right) break;
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ret[i][j] = v[i][j];
            }
        }
        return ret;
    }
};

int main()
{
    Solution s;
    int n = 3;
    vector<vector<int>> r = s.generateMatrix(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << r[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int begin = 0, end = -1;
        int max = nums[0], min = nums[n - 1];
        for (int i = 0; i < n; i++)
        {
            if (nums[i] < max)
            {
                end = i;
            }
            else
            {
                max = nums[i];
            }
        }
        for (int i = n - 1; i >= 0; i--)
        {
            if (nums[i] > min)
            {
                begin = i;
            }
            else
            {
                min = nums[i];
            }
        }
        return end - begin + 1;
    }
};